package n2823;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Node{
	int value;
	int place;
}

public class Main {

	
	
	
	static Node[] bigHeap=new Node[1000001];
	
	static Node[] smallHeap=new Node[1000001];
	
	static int bigCount=0,smallCount=0;
	static void fixup(Node[] heap,int k,boolean flag)
	{
		Node data=heap[k];
		int s=k>>1;
		while(s>=0)
		{
			if(flag)
			{
				if(heap[s].value<data.value)heap[k]=heap[s];
				else break;
			}else{
				if(heap[s].value>data.value)heap[k]=heap[s];
				else break;
			}
			k=s;
			if(s==0)break;
			s=k>>1;
		}
		heap[k]=data;
	}
	
	static void fixdown(Node[] heap,int k,int end,boolean flag)
	{
		Node data=heap[k];
		int s=k<<1;
		while(s<end)
		{
			if(flag)
			{
				if(s+1<end&&heap[s+1].value>heap[s].value)s++;
				if(heap[s].value>data.value)heap[k]=heap[s];
				else break;
			}else{
				if(s+1<end&&heap[s+1].value<heap[s].value)s++;
				if(heap[s].value<data.value)heap[k]=heap[s];
				else break;
			}
			k=s;
			s=k<<1;
		}
		heap[k]=data;
	}
	
	static void add(Node[] heap,int end,Node node,boolean flag)
	{
		heap[end-1]=node;
		fixup(heap,end-1,flag);
	}
	
	
	static Node pop(Node[] heap,int end,boolean flag)
	{
		Node result=heap[0];
		heap[0]=heap[end-1];
		heap[end-1]=null;
		fixdown(heap, 0, end-1, flag);
		return result;
	}
	
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception {

		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		String line=bf.readLine();
		StringTokenizer st=new StringTokenizer(line);
		int n=Integer.parseInt(st.nextToken());
		int k=Integer.parseInt(st.nextToken());
		st=new StringTokenizer(bf.readLine());
		int big[]=new int[n-k+1];
		int small[]=new int[n-k+1];
		for(int i=0;i<n;i++)
		{
			int cur=Integer.parseInt(st.nextToken());
			Node node=new Node();
			node.value=cur;
			node.place=i;
			
			add(bigHeap, ++bigCount, node, true);
			add(smallHeap,++smallCount,node,false);
			
			if(i>=k-1){
				
				Node tmp=bigHeap[0];
				while(tmp.place<=i-k)
				{
					pop(bigHeap, bigCount--, true);
					tmp=bigHeap[0];
				}
				big[i-k+1]=tmp.value;
				tmp=smallHeap[0];
				while(tmp.place<=i-k)
				{
					pop(smallHeap, smallCount--, false);
					tmp=smallHeap[0];
				}
				small[i-k+1]=tmp.value;
			}
			
			
			
		}
		
		
		
		for(int i=0;i<n-k+1;i++)
			System.out.print(small[i]+((i!=n-k)?" ":""));
		System.out.println();
		for(int i=0;i<n-k+1;i++)
			System.out.print(big[i]+((i!=n-k)?" ":""));
		
	}

}
